#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;


//int GetRandom(vector<int>& arr, int left, int right)
//{
//	int pos = left + rand() % (right - left + 1);
//	return arr[pos];
//}
//
//void QuickSort(vector<int>& arr, int left, int right)
//{
//	if (left >= right) return;
//	int key = GetRandom(arr, left, right);
//	int i = left, curL = left - 1, curR = right + 1;
//	while (i < right)
//	{
//		if (arr[i] < key)
//			swap(arr[++curL], arr[i++]);
//		else if (arr[i] > key)
//			swap(arr[--curR], arr[i]);
//		else i++;
//	}
//
//	QuickSort(arr, left, curL);
//	QuickSort(arr, curR, right);
//}
//
//
//int main()
//{
//	//int n; cin >> n;
//	//vector<int> arr; arr.resize(n);
//	//for (int i = 0; i < n; i++)
//	//	cin >> arr[i];
//	vector<int> arr = { 12, 34 ,23 ,121 ,1 };
//	srand(time(nullptr));
//	QuickSort(arr, 0, arr.size() - 1);
//
//	for (auto x : arr)
//		std::cout << x << " ";
//	return 0;
//}


//class Solution {
//public:
//    int GetRandom(vector<int>& nums, int l, int r)
//    {
//        int pos = l + rand() % (r - l + 1);
//        return nums[pos];
//    }
//    void QSort(vector<int>& nums, int l, int r)
//    {
//        if (l >= r) return;
//        int key = GetRandom(nums, l, r);
//        int i = l, left = l - 1, right = r + 1;
//        while (i < right)
//        {
//            if (nums[i] > key)
//                swap(nums[--right], nums[i]);
//            else if (nums[i] == key)
//                i++;
//            else
//                swap(nums[++left], nums[i++]);
//        }
//        QSort(nums, l, left);
//        QSort(nums, right, r);
//    }
//
//    vector<int> sortArray(vector<int>& nums) {
//        QSort(nums, 0, nums.size() - 1);
//        return nums;
//    }
//};



//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        int left = -1, right = nums.size(), i = 0;
//        while (i < right)
//        {
//            if (nums[i] == 0)
//                swap(nums[++left], nums[i++]);
//            else if (nums[i] == 2)
//                swap(nums[--right], nums[i]);
//            else i++;
//        }
//    }
//};




//class Solution {
//public:
//    int GetRandom(vector<int>& nums, int l, int r)
//    {
//        int pos = l + rand() % (r - l + 1);
//        return nums[pos];
//    }
//
//    int QSort(vector<int>& nums, int l, int r, int k)
//    {
//        if (k == 0) return nums[l];
//        int key = GetRandom(nums, l, r);
//        int i = l, left = l - 1, right = r + 1;
//        while (i < right)
//        {
//            if (nums[i] > key)
//                swap(nums[i], nums[--right]);
//            else if (nums[i] == key)
//                i++;
//            else
//                swap(nums[i++], nums[++left]);
//        }
//        // [l, left] [left + 1, right - 1] [right, r]
//        int gap1 = r - right + 1, gap2 = r - left;
//        if (gap1 >= k)
//            return QSort(nums, right, r, k);
//        else if (gap2 >= k) return key;
//        else return QSort(nums, l, left, k - gap2);
//    }
//
//    int findKthLargest(vector<int>& nums, int k) {
//        srand(time(nullptr));
//        return QSort(nums, 0, nums.size() - 1, k);
//    }
//};




//class Solution {
//public:
//    vector<int> smallestK(vector<int>& arr, int k) {
//        srand(time(nullptr));
//        Qsort(arr, 0, arr.size() - 1);
//
//        vector<int> ret;
//        ret.resize(k);
//        for (int i = 0; i < k; i++)
//            ret[i] = arr[i];
//        return ret;
//    }
//
//
//    void Qsort(vector<int>& arr, int l, int r)
//    {
//        if (l >= r) return;
//        int key = GetRandom(arr, l, r);
//        int i = l, left = l - 1, right = r + 1;
//        while (i < right)
//        {
//            if (arr[i] > key)
//                swap(arr[i], arr[--right]);
//            else if (arr[i] == key)
//                i++;
//            else
//                swap(arr[i++], arr[++left]);
//        }
//
//        Qsort(arr, l, left);
//        Qsort(arr, right, r);
//    }
//
//    int GetRandom(vector<int>& arr, int l, int r)
//    {
//        int pos = l + rand() % (r - l + 1);
//        return arr[pos];
//    }
//};




